/**
 * 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
 *https://leetcode.cn/problems/trapping-rain-water/description/j
 */
class TrapPoniter {
    public int trap(int[] height) {
        int ret = 0;
        int len = height.length;
        int left = 0;
        int right = len-1;
        int leftMax = 0;
        int rightMax = 0;
        while(left <= right) {
            if(height[left] < height[right]) {
                left++;
                if(leftMax > height[left-1]) {
                    ret += (leftMax-height[left-1]);
                } else {
                    leftMax = height[left-1];
                }
                
            } else {
                right--;
                if(rightMax > height[right+1]) {
                    ret += (rightMax-height[right+1]);
                } else {
                    rightMax = height[right+1];
                }
            }
        }
        return ret;
    }
}